package leetcode.top100;

/**
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
 * 可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,4,2,2]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: [3,1,3,4,2]
 * 输出: 3
 * 说明：
 * <p>
 * 不能更改原数组（假设数组是只读的）。
 * 只能使用额外的 O(1) 的空间。
 * 时间复杂度小于 O(n2) 。
 * 数组中只有一个重复的数字，但它可能不止重复出现一次。
 * <p>
 * 其他相关问题见{@link leetcode.a_总结分布.Code02_数组中缺失或重复数字}
 *
 * @date 2020/4/15 13:18
 */
public class Code287_FindRepeatNum2 {
    /**
     * 方式1：使用set，时空都是O(n)
     * 方式2：排序
     * 方式3：使用标记法
     * n+1个数范围是 1-n,也就是n个数范围是1- n-1
     */
    public int findDuplicate3(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        //把1- n-1归位标记到1- n-1索引
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]);
            if (nums[index] < 0) {
                return index;
            } else {
                nums[index] = -nums[index];
            }
        }
        //never can reach here
        return -1;
    }

    /**
     * 方式4:标记法2
     * n+1个数范围是 1-n,也就是n个数范围是1- n-1
     */
    public int findDuplicate4(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        //因为不含有0，所以把1-n-1位置元素归为到1-n-1位置，最后单独处理0号位置元素
        for (int i = 1; i < nums.length; i++) {
            //查看当前位置i的元素num[i]是否为i
            while (nums[i] != i) {
                //index为要交换的位置
                int index = nums[i];
                //如果这个位置已经满足归位，那么就是第二次归位，找到目标元素了
                if (nums[index] == index) return index;
                swap(nums, index, i);
            }
        }
        int index = nums[0];
        if (index == nums[index]) return index;
        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        if (i != j) {
            nums[i] = nums[i] ^ nums[j];
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 2};
        System.out.println(new Code287_FindRepeatNum2().findDuplicate4(arr));
//        System.out.println(duplicate(new int[]{1,0, 1}));
    }


}
